Functional Decomposition of Sparse Polynomials

Abstract: We consider the algorithmic problem of the functional decomposition of sparse polynomials.

For example, (very) given a very high degree $(5*2^100)$ and very sparse (7 terms) polynomial like

$f(x) = x^(5*2^100) + 15*x^(2^102+2^47) + 90*x^(2^101+2^100 + 2^48) + 270*x^(2^101 + 3*2^47) + 405*x^(2^100 + 2^49) + 243*x^(5* 2^47) + 1$

we ask how to quickly determine whether it can be be quickly written as a composition of lower degree polynomials such as

$f(x) = g(h(x)) = g o h = (x^5+1) o (x^(2^100)+3x^(2^{47})).$

Mathematically, Erdos (1949), Schinzel(1987), and Zannier(2008) have made major progress in showing that polynomial roots and functional decompositions of sparse polynomials, remain (fairly) sparse, unlike factorizations into irreducibels for example.

Computationally, we have had algorithms for functional decomposition of dense polynomials since Barton & Zippel (1976), though the first polynomial-time algorithms did not arrive until Kozen & Landau (1986}) and a linear-time algorithm by Gathen et al. (1987), at least in the ``tame'' case, where the characteristic of the underlying field does not divide the degree.

Algorithms for polynomial decomposition that exploit sparsity have remained elusive until now. We demonstrate new algorithms which provide very fast sparsity-sensitive solutions to some of these problems. But important open algorithmic problems remain, including proving indecomposibility, and more general sparse functional decomposition. And there is still considerable room to tighten sparsity bounds in the underlying mathematics and/or the implied complexities.

This is ongoing work with Saiyue Liu (UBC) and Daniel S. Roche (USNA).

algebraic geometrynumber theory

Audience: researchers in the discipline

---

SFU NT-AG seminar

Series comments: The Number Theory and Algebraic Geometry (NT-AG) seminar is a research seminar dedicated to topics related to number theory and algebraic geometry hosted by the NT-AG group (Nils Bruin, Imin Chen, Stephen Choi, Katrina Honigs, Nathan Ilten, Marni Mishna).

We acknowledge the support of PIMS, NSERC, and SFU.

For Fall 2025, the organizers are Katrina Honigs and Peter McDonald.

We normally meet in-person in the indicated room. For online editions, we use Zoom and distribute the link through the mailing list. If you wish to be put on the mailing list, please subscribe to ntag-external using lists.sfu.ca

---